package main.leetcode.clockin.July;

/**
 * 97. 交错字符串
 *
 * <p>给定三个字符串 s1, s2, s3, 验证 s3 是否是由 s1 和 s2 交错组成的。
 *
 * <p>示例 1: 输入: s1 = "aabcc", s2 = "dbbca", s3 = "aadbbcbcac" 输出: true
 *
 * <p>示例 2: 输入: s1 = "aabcc", s2 = "dbbca", s3 = "aadbbbaccc" 输出: false
 */
public class day18 {
    public static void main(String[] args) {
        System.out.println(new day18().isInterleave("dbbca", "aabcc", "aadbbcbcac"));
        System.out.println(new day18().isInterleave("aabcc", "dbbca", "aadbbbaccc"));
        System.out.println(new day18().isInterleave("a", "", "c"));
        System.out.println(new day18().isInterleave("", "", "c"));
    }

    /** dfs，记忆化搜索 */
    public boolean isInterleave(String s1, String s2, String s3) {
        int m = s1.length();
        int n = s2.length();
        if (m + n != s3.length()) {
            return false;
        }
        Boolean[][] memo = new Boolean[m + 1][n + 1];
        return dfs(memo, s1, 0, s2, 0, s3, 0);
    }

    private boolean dfs(Boolean[][] memo, String s1, int i, String s2, int j, String s3, int k) {
        if (memo[i][j] != null) {
            return memo[i][j];
        }
        if (k == s3.length()) {
            return memo[i][j] = i == s1.length() && j == s2.length();
        }

        if (i < s1.length()) {
            if (memo[i][j] =
                    s1.charAt(i) == s3.charAt(k) && dfs(memo, s1, i + 1, s2, j, s3, k + 1)) {
                return memo[i][j] = true;
            }
        }

        if (j < s2.length()) {
            if (memo[i][j] =
                    s2.charAt(j) == s3.charAt(k) && dfs(memo, s1, i, s2, j + 1, s3, k + 1)) {
                return memo[i][j] = true;
            }
        }
        return memo[i][j] = false;
    }

    //    /** dp */
    //    public boolean isInterleave(String s1, String s2, String s3) {
    //        int m = s1.length();
    //        int n = s2.length();
    //        if (m + n != s3.length()) {
    //            return false;
    //        }
    //        boolean[][] dp = new boolean[m + 1][n + 1];
    //        dp[0][0] = true;
    //        for (int i = 1; i <= m && s1.charAt(i - 1) == s3.charAt(i - 1); ++i) {
    //            dp[i][0] = true;
    //        }
    //        for (int i = 1; i <= n && s2.charAt(i - 1) == s3.charAt(i - 1); ++i) {
    //            dp[0][i] = true;
    //        }
    //        for (int i = 1; i <= m; ++i) {
    //            for (int j = 1; j <= n; ++j) {
    //                dp[i][j] =
    //                        dp[i - 1][j] && s1.charAt(i - 1) == s3.charAt(i + j - 1)
    //                                || dp[i][j - 1] && s2.charAt(j - 1) == s3.charAt(i + j - 1);
    //            }
    //        }
    //        return dp[m][n];
    //    }

    //    /** dp —— 滚动数组 */
    //    public boolean isInterleave(String s1, String s2, String s3) {
    //        int m = s1.length();
    //        int n = s2.length();
    //        if (m + n != s3.length()) {
    //            return false;
    //        }
    //        if (m > n) {
    //            return isInterleave(s2, s1, s3);
    //        }
    //        boolean[] dp = new boolean[n + 1];
    //        dp[0] = true;
    //        for (int i = 1; i <= n && s2.charAt(i - 1) == s3.charAt(i - 1); ++i) {
    //            dp[i] = true;
    //        }
    //        for (int i = 1; i <= m; ++i) {
    //            for (int j = 1; j <= n; ++j) {
    //                int k = i + j - 1;
    //                dp[j] =
    //                        dp[j] && s1.charAt(i - 1) == s3.charAt(k)
    //                                || dp[j - 1] && s2.charAt(j - 1) == s3.charAt(k);
    //            }
    //        }
    //        return dp[n];
    //    }
}
